#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		int len = nums.size();
		if (len < 2) return {};

		sort(nums.begin(), nums.end());
		if (nums[0] > 0 || nums[len - 1] < 0) return {};

		vector<vector<int>> res;
		vector<int> temp;
		int first, second, third;
		long long int target;
		for (first = 0;first < len;first++)
		{
			if (nums[first] > 0) break;
			if (first > 0 && nums[first] == nums[first - 1])
			{
				cout << nums[first] << "***" << endl;
				continue;
			}
			target = -nums[first];
			second = first + 1;
			third = len - 1;

			while (second<third)
			{
				if (nums[second] + nums[third] == target)
				{
					temp.push_back(nums[first]);
					temp.push_back(nums[second]);
					temp.push_back(nums[third]);
					res.push_back(temp);
					temp.clear();

					second++;
					while (second > 0 && nums[second] == nums[second - 1] && second+1 < third)
					{
						second++;
					}
					third--;
					while (third < len - 1 && nums[third] == nums[third + 1] && second < third-1)
					{
						third--;
					}
				}
				else if (nums[second] + nums[third] > target)
				{
					third--;
					while (third < len - 1 && nums[third] == nums[third + 1] && second < third)
					{
						third--;
					}
				}
				else
				{
					second++;
					while (second > 0 && nums[second] == nums[second - 1] && second < third)
					{
						second++;
					}
				}
			}
		}
		return res;
	}
};

int main()
{
	vector<int> arr{ 34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49};
	Solution s;
	vector<vector<int>> res = s.threeSum(arr);
	for (auto it = res.begin();it != res.end();it++)
	{
		for (auto iv = it->begin();iv != it->end();iv++)
		{
			cout << (*iv) << " ";
		}
		cout << endl;
	}
	return 0;
}
